package com.shuang.graph13;

import java.util.*;
/*
* 冗余连接II。找到入度为2的节点删除靠后的一条边 但可能有几种情况
1 没有入度为2的节点
2 有入度为2的节点但是如果要删靠后的边的话 有向图还是成环的 所以只能删除入度为2节点的另一条边
*
* 判断是否成环（并查集）
*/
 
public class Main {
 
    /** 并查集模板 */
    static class Disjoint {
 
        private final int[] father;
 
        public Disjoint(int n) {
            father = new int[n];
            for (int i = 0; i < n; i++) {
                father[i] = i;
            }
        }
 
        public void join(int n, int m) {
            n = find(n);
            m = find(m);
            if (n == m) return;
            father[n] = m;
        }
 
        public int find(int n) {
            return father[n] == n ? n : (father[n] = find(father[n]));
        }
 
        public boolean isSame(int n, int m) {
            return find(n) == find(m);
        }
    }
 
    public static class pair {
        int first;
        int second;
 
        public pair(int s, int t) {
            first = s;
            second = t;
        }
    }
 
    public static void main(String[] args) {
        //输入
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
 
        //用来存有向图的边s t
        List<pair> edges = new ArrayList<>();
 
        //定义一个数组用来计算每个节点入度
        int[] indgree = new int[n + 1];
 
        //输入s t 存边和记录入度
        for (int i = 0; i < n; i++) {
            int s = scanner.nextInt();
            int t = scanner.nextInt();
 
            edges.add(new pair(s, t));
 
            //下标代表入度的节点 值为度
            indgree[t]++;
        }
 
        //定义一个集合用来存放入度为2的两条边的编号
        List<Integer> visited = new ArrayList<>();
 
        //遍历所有边 找入度为2的节点分情况判断
        for (int i = 0; i < n; i++) {
 
            if (indgree[edges.get(i).second] == 2) {
                visited.add(i);
            }
        }
 
        if (visited.size() > 0) {
            //说明上面找到了入度为2的节点
            //函数功能为删除靠后的那条边后 判断是否是树（不成环）
            if (isTreeAfterDelEdge(edges, visited.get(1))) {
                System.out.print(
                        edges.get(visited.get(1)).first + " " + edges.get(visited.get(1)).second);
                return;
            } else {
                //删完不是树只能输出前面那条边
                System.out.print(
                        edges.get(visited.get(0)).first + " " + edges.get(visited.get(0)).second);
                return;
            }
        }
 
        //说明没有入度为2的节点
        //可以用并查集模板判断成环 虽然是有向图但是成环了就不管方向了 解除环即可
        Disjoint joint = new Disjoint(n + 1);
        //遍历所有边
        for (int i = 0; i < n; i++) {
            if (joint.isSame(edges.get(i).first, edges.get(i).second)) {
                System.out.print(edges.get(i).first + " " + edges.get(i).second);
                return;
            } else {
                joint.join(edges.get(i).first, edges.get(i).second);
            }
        }
    }
 
    public static boolean isTreeAfterDelEdge(List<pair> edges, int num) {
 
        Disjoint joint = new Disjoint(edges.size() + 1);
 
        //遍历所有边
        for (int i = 0; i < edges.size(); i++) {
            if (i == num) {
                //当遍历到传进来的编号的边时直接跳过 相当于删除这条边了
                continue;
            }
            //将剩下编号的边进行并查集判断成环
            if (joint.isSame(edges.get(i).first, edges.get(i).second)) {
                return false;
            } else {
                joint.join(edges.get(i).first, edges.get(i).second);
            }
        }
 
        return true;
    }
}
 